#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ORDER 4                  // B+树的阶数
#define MIN_KEYS (ORDER - 1) / 2 // 最小关键字数

// B+树结点结构
typedef struct BPlusTreeNode
{
    bool isLeaf;                               // 是否为叶子结点
    int numKeys;                               // 当前关键字数量
    int keys[ORDER];                           // 关键字数组
    struct BPlusTreeNode *children[ORDER + 1]; // 子结点指针数组
    struct BPlusTreeNode *next;                // 叶子结点的下一个结点指针
} BPlusTreeNode;

// 创建新结点
BPlusTreeNode *createNode(bool isLeaf)
{
    BPlusTreeNode *node = (BPlusTreeNode *)malloc(sizeof(BPlusTreeNode));
    node->isLeaf = isLeaf;
    node->numKeys = 0;
    node->next = NULL;

    for (int i = 0; i < ORDER + 1; i++)
    {
        node->children[i] = NULL;
    }

    return node;
}

// 在叶子结点中插入关键字
void insertIntoLeaf(BPlusTreeNode *leaf, int key)
{
    int i = leaf->numKeys - 1;
    while (i >= 0 && key < leaf->keys[i])
    {
        leaf->keys[i + 1] = leaf->keys[i];
        i--;
    }
    leaf->keys[i + 1] = key;
    leaf->numKeys++;
}

// 分裂叶子结点
BPlusTreeNode *splitLeafNode(BPlusTreeNode *leaf, int *promotedKey)
{
    BPlusTreeNode *newLeaf = createNode(true);
    int splitIndex = ORDER / 2; // 分裂位置

    // 复制后半部分关键字到新叶子结点
    for (int i = splitIndex; i < ORDER; i++)
    {
        newLeaf->keys[i - splitIndex] = leaf->keys[i];
    }
    newLeaf->numKeys = ORDER - splitIndex;
    leaf->numKeys = splitIndex;

    // 设置叶子结点链表
    newLeaf->next = leaf->next;
    leaf->next = newLeaf;

    // 提升的关键字是右结点的第一个关键字
    *promotedKey = newLeaf->keys[0];
    return newLeaf;
}

// 分裂内部结点
BPlusTreeNode *splitInternalNode(BPlusTreeNode *node, int *promotedKey)
{
    BPlusTreeNode *newNode = createNode(false);
    int splitIndex = ORDER / 2; // 分裂位置

    // 提升的键是中间键
    *promotedKey = node->keys[splitIndex];

    // 复制后半部分键和子结点到新结点
    for (int i = splitIndex + 1; i < node->numKeys; i++)
    {
        newNode->keys[i - splitIndex - 1] = node->keys[i];
    }
    for (int i = splitIndex + 1; i <= node->numKeys; i++)
    {
        newNode->children[i - splitIndex - 1] = node->children[i];
    }

    newNode->numKeys = node->numKeys - splitIndex - 1;
    node->numKeys = splitIndex;
    return newNode;
}

// 在内部结点中插入键和子结点
void insertIntoInternal(BPlusTreeNode *node, int key, BPlusTreeNode *child)
{
    int i = node->numKeys - 1;

    // 找到插入位置
    while (i >= 0 && key < node->keys[i])
    {
        node->keys[i + 1] = node->keys[i];
        node->children[i + 2] = node->children[i + 1];
        i--;
    }

    node->keys[i + 1] = key;
    node->children[i + 2] = child;
    node->numKeys++;
}

// 向B+树插入键
BPlusTreeNode *insert(BPlusTreeNode *root, int key)
{
    // 如果树为空
    if (root == NULL)
    {
        root = createNode(true);
        root->keys[0] = key;
        root->numKeys = 1;
        return root;
    }

    // 找到合适的叶子结点
    BPlusTreeNode *current = root;
    BPlusTreeNode *parent = NULL;
    int parentIndex = 0;

    while (!current->isLeaf)
    {
        parent = current;
        int i = 0;
        while (i < current->numKeys && key >= current->keys[i])
        {
            i++;
        }
        current = current->children[i];
        parentIndex = i;
    }

    // 在叶子结点中插入键
    insertIntoLeaf(current, key);

    // 如果叶子结点未满，直接返回
    if (current->numKeys < ORDER)
    {
        return root;
    }

    // 分裂叶子结点
    int promotedKey;
    BPlusTreeNode *newLeaf = splitLeafNode(current, &promotedKey);

    // 如果没有父结点（当前结点是根）
    if (parent == NULL)
    {
        BPlusTreeNode *newRoot = createNode(false);
        newRoot->keys[0] = promotedKey;
        newRoot->children[0] = current;
        newRoot->children[1] = newLeaf;
        newRoot->numKeys = 1;
        return newRoot;
    }

    // 在父结点中插入提升的键和新结点
    insertIntoInternal(parent, promotedKey, newLeaf);

    // 向上递归处理溢出
    while (parent != NULL && parent->numKeys == ORDER)
    {
        int newPromotedKey;
        BPlusTreeNode *newSibling = splitInternalNode(parent, &newPromotedKey);

        // 如果当前结点是根
        if (parent == root)
        {
            BPlusTreeNode *newRoot = createNode(false);
            newRoot->keys[0] = newPromotedKey;
            newRoot->children[0] = parent;
            newRoot->children[1] = newSibling;
            newRoot->numKeys = 1;
            return newRoot;
        }

        // 继续向上插入
        BPlusTreeNode *grandParent = root;
        while (grandParent != NULL)
        {
            bool found = false;
            for (int i = 0; i <= grandParent->numKeys; i++)
            {
                if (grandParent->children[i] == parent)
                {
                    insertIntoInternal(grandParent, newPromotedKey, newSibling);
                    found = true;
                    break;
                }
            }
            if (found)
                break;
            grandParent = grandParent->children[0]; // 简化搜索
        }

        parent = grandParent;
    }

    return root;
}

// 打印B+树（叶子结点遍历）
void printBPlusTree(BPlusTreeNode *root)
{
    if (root == NULL)
    {
        printf("Tree is empty\n");
        return;
    }

    // 找到第一个叶子结点
    BPlusTreeNode *current = root;
    while (!current->isLeaf)
    {
        current = current->children[0];
    }

    // 遍历所有叶子结点
    printf("Leaf node values: ");
    while (current != NULL)
    {
        for (int i = 0; i < current->numKeys; i++)
        {
            printf("%d ", current->keys[i]);
        }
        current = current->next;
    }
    printf("\n");
}

// 主函数测试
int main()
{
    BPlusTreeNode *root = NULL;

    // 测试插入序列
    int arr[] = {10, 20, 5, 6, 12, 30, 7, 17, 3, 1, 8, 25, 15};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Inserting values: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
        root = insert(root, arr[i]);
    }
    printf("\n");

    // 打印B+树（叶子结点遍历）
    printBPlusTree(root);

    return 0;
}